from pythonds import BinaryTree
from collections import deque
def buildTree(preorder,inorder):
    # 递归中止条件 树为空
    if not preorder or not inorder:
        return None;

    # 根节点的值为前序遍历的第一个元素值
    rootVal=preorder[0]
    # 创建根节点
    root=BinaryTree(rootVal)

    # 用根节点的值去中序数组中查找对应元素下标
    midIndex=inorder.index(rootVal)

    # 找出中序遍历的左子树和右子树
    # 左子树区间为[0,midInex)] 右子树区间为[midIndex+1,n-1]
    inorderLeft=inorder[:midIndex]
    inorderRight=inorder[midIndex+1:]

    # 找出前序遍历的左子树和右子树
    # 前序遍历和中序遍历的左子树和右子树长度相等，所以可以通过中序遍历左右子树的长度来确定前序遍历左右子树的位置
    proorderLeft=preorder[1:len(inorderLeft)+1]
    proorderRight=preorder[len(inorderLeft)+1:]

    # 递归遍历左子树
    root.leftChild=buildTree(proorderLeft,inorderLeft)
    # 递归遍历右子树
    root.rightChild=buildTree(proorderRight,inorderRight)

    return root
def preorderTraversl(root):
    # 保存结果
    result=[]

    def traversal(root):
        # 确定终止条件
        if root==None:
            return
        # 前序遍历顺序 中左右
        result.append(root.key) #中
        traversal(root.getLeftChild()) # 左
        traversal(root.getRightChild()) # 右
    # 进入traversal()方法
    traversal(root)
    return result
# 中序遍历 左中右
def inorderTraversal(root):
    # 保存结果
    result=[]

    def traversal(root):
        # 终止条件
        if root==None:
            return
        # 中序遍历顺序 左中右
        traversal(root.getLeftChild()) #左
        result.append(root.key) #中
        traversal(root.getRightChild()) #右
    traversal(root)
    return result
# 后序遍历 左右中
def afterorderTraversal(root):
    # 保存结果
    result=[]
    def traversal(root):
        # 终止条件
        if root==None:
            return
        # 后序遍历顺序 左右中
        traversal(root.getLeftChild())
        traversal(root.getRightChild())
        result.append(root.key)
    traversal(root)
    return result
def levelOrder(root):
    results=[]
    if not root:
        return results;
    que=deque([root])

    while que:
        size=len(que)
        result=[]
        for _ in range(size):
            cur=que.popleft(); # 移去并且返回一个元素，deque 最左侧的那一个。 如果没有元素的话，就引发 IndexError。
            result.append(cur.key);
            if cur.getLeftChild():
                que.append(cur.getLeftChild())
            if cur.getRightChild():
                que.append(cur.getRightChild())
        results.append(result)
    return results
root=buildTree([4,2,1,3,6,5,7],[1,2,3,4,5,6,7])
print("先序遍历:",preorderTraversl(root))
print("中序遍历:",inorderTraversal(root))
print("后序遍历:",afterorderTraversal(root))
print("层序遍历:",levelOrder(root))

root2=buildTree(['A','B','D','E','J','C','F','I','G'],['D','B','J','E','A','F','I','C','G'])
preorder=preorderTraversl(root2)
print("先序遍历:",end='')
print(','.join(preorder))
inorder=inorderTraversal(root2)
print("中序遍历:",end='')
print(','.join(inorder))
print("后序遍历:",afterorderTraversal(root2))
print("层序遍历:",levelOrder(root2))
